home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / CONTAIN.C < prev    next >
Text File  |  1987-03-13  |  10KB  |  324 lines
  1. /*
  2.     contain.c -- set containment routines
  3.  
  4.     These are complex routines for performing containment over a
  5.     family of sets, but they have the advantage of being much faster
  6.     than a straightforward n*n routine.
  7.  
  8.     First the cubes are sorted by size, and as a secondary key they are
  9.     sorted so that if two cubes are equal they end up adjacent.  We can
  10.     than quickly remove equal cubes from further consideration by
  11.     comparing each cube to its neighbor.  Finally, because the cubes
  12.     are sorted by size, we need only check cubes which are larger (or
  13.     smaller) than a given cube for containment.
  14. */
  15.  
  16. #include "espresso.h"
  17.  
  18.  
  19. /*
  20.     sf_contain -- perform containment on a set family (delete sets which
  21.     are contained by some larger set in the family).  No assumptions are
  22.     made about A, and the result will be returned in decreasing order of
  23.     set size.
  24. */
  25. pset_family sf_contain(A)
  26. INOUT pset_family A;            /* disposes of A */
  27. {
  28.     int cnt;
  29.     pset *A1;
  30.     pset_family R;
  31.  
  32.     A1 = sf_sort(A, descend);           /* sort into descending order */
  33.     cnt = rm_equal(A1, descend);        /* remove duplicates */
  34.     cnt = rm_contain(A1);               /* remove contained sets */
  35.     R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
  36.     sf_free(A);
  37.     return R;
  38. }
  39.  
  40.  
  41. /* sf_dupl -- delete duplicate sets in a set family */
  42. pset_family sf_dupl(A)
  43. INOUT pset_family A;            /* disposes of A */
  44. {
  45.     register int cnt;
  46.     register pset *A1;
  47.     pset_family R;
  48.  
  49.     A1 = sf_sort(A, descend);           /* sort the set family */
  50.     cnt = rm_equal(A1, descend);        /* remove duplicates */
  51.     R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
  52.     sf_free(A);
  53.     return R;
  54. }
  55.  
  56.  
  57. /*
  58.     sf_union -- form the contained union of two set families (delete
  59.     sets which are contained by some larger set in the family).  A and
  60.     B are assumed already sorted in decreasing order of set size (and
  61.     the SIZE field is assumed to contain the set size), and the result
  62.     will be returned sorted likewise.
  63. */
  64. pset_family sf_union(A, B)
  65. INOUT pset_family A, B;         /* disposes of A and B */
  66. {
  67.     int cnt;
  68.     pset_family R;
  69.     pset *A1 = sf_list(A), *B1 = sf_list(B), *E1;
  70.  
  71.     E1 = (pset *) alloc((max(A->count,B->count)+1) * sizeof(pset));
  72.     cnt = rm2_equal(A1, B1, E1, descend);
  73.     cnt += rm2_contain(A1, B1) + rm2_contain(B1, A1);
  74.     R = sf_merge(A1, B1, E1, cnt, A->sf_size);
  75.     sf_free(A); sf_free(B);
  76.     return R;
  77. }
  78.  
  79. /*
  80.     d1merge -- perform an efficient distance-1 merge of cubes of A
  81. */
  82. pset_family d1merge(A, var)
  83. INOUT pset_family A;            /* disposes of A */
  84. IN int var;
  85. {
  86.     register pset pr, p, last, *A1;
  87.     int cnt;
  88.     pset_family R;
  89.  
  90.     set_copy(cube.temp[0], cube.var_mask[var]);
  91.     A1 = sf_list(A);
  92.     qsort((char *) A1, A->count, sizeof(pset), d1_order);
  93.  
  94.     cnt = A->count - d1_rm_equal(A1);
  95.     R = sf_new(cnt, A->sf_size);
  96.     R->count = cnt;
  97.     pr = R->data;
  98.     foreach_active_set(A, last, p) {
  99.         INLINEset_copy(pr, p);
  100.         pr += R->wsize;
  101.     }
  102.  
  103.     mem_free((char *) A1);
  104.     sf_free(A);
  105.     return R;
  106. }
  107. /* d1_rm_equal -- distance-1 merge remove equal */
  108. int d1_rm_equal(A1)
  109. IN pcube *A1;
  110. {
  111.     register int xi, xj, del = 0;
  112.     if (*A1 != NULL) {                  /* If more than one set */
  113.         for(xi = 0, xj = 1; A1[xj] != NULL; xj++)
  114.             if (d1_order(A1+xi, A1+xj) == 0) {
  115.                 INLINEset_or(A1[xi], A1[xi], A1[xj]);
  116.                 RESET(A1[xj], ACTIVE);
  117.                 del++;
  118.             } else {
  119.                 SET(A1[xi], ACTIVE);
  120.                 xi = xj;
  121.             }
  122.         SET(A1[xi], ACTIVE);
  123.     }
  124.     return del;
  125. }
  126.  
  127.  
  128. /* rm_equal -- scan a sorted array of set pointers for duplicate sets */
  129. int rm_equal(A1, compare)
  130. INOUT pset *A1;                 /* updated in place */
  131. IN int (*compare)();
  132. {
  133.     register pset *p, *pdest = A1;
  134.  
  135.     if (*A1 != NULL) {                  /* If more than one set */
  136.         for(p = A1+1; *p != NULL; p++)
  137.             if ((*compare)(p, p-1) != 0)
  138.                 *pdest++ = *(p-1);
  139.         *pdest++ = *(p-1);
  140.         *pdest = NULL;
  141.     }
  142.     return pdest - A1;
  143. }
  144.  
  145.  
  146. /* rm_contain -- perform containment over a sorted array of set pointers */
  147. int rm_contain(A1)
  148. INOUT pset *A1;                 /* updated in place */
  149. {
  150.     register pset *pa, *pb, *pcheck, a, b;
  151.     pset *pdest = A1;
  152.     int last_size = -1;
  153.  
  154.     /* Loop for all cubes of A1 */
  155.     for(pa = A1; (a = *pa++) != NULL; ) {
  156.         /* Update the check pointer if the size has changed */
  157.         if (SIZE(a) != last_size)
  158.             last_size = SIZE(a), pcheck = pdest;
  159.         for(pb = A1; pb != pcheck; ) {
  160.             b = *pb++;
  161.             INLINEsetp_implies(a, b, /* when_false => */ continue);
  162.             goto lnext1;
  163.         }
  164.         /* Set was not contained by some earlier set, so save it */
  165.         *pdest++ = a;
  166.     lnext1: ;
  167.     }
  168.  
  169.     *pdest = NULL;
  170.     return pdest - A1;
  171. }
  172.  
  173.  
  174. /* rm2_equal -- check two sorted arrays of set pointers for equal cubes */
  175. int rm2_equal(A1, B1, E1, compare)
  176. INOUT register pset *A1, *B1;           /* updated in place */
  177. OUT pset *E1;
  178. IN int (*compare)();
  179. {
  180.     register pset *pda = A1, *pdb = B1, *pde = E1;
  181.  
  182.     /* Walk through the arrays advancing pointer to larger cube */
  183.     for(; *A1 != NULL && *B1 != NULL; )
  184.         switch((*compare)(A1, B1)) {
  185.             case -1:    /* "a" comes before "b" */
  186.                 *pda++ = *A1++; break;
  187.             case 0:     /* equal cubes */
  188.                 *pde++ = *A1++; B1++; break;
  189.             case 1:     /* "a" is to follow "b" */
  190.                 *pdb++ = *B1++; break;
  191.         }
  192.  
  193.     /* Finish moving down the pointers of A and B */
  194.     while (*A1 != NULL)
  195.         *pda++ = *A1++;
  196.     while (*B1 != NULL)
  197.         *pdb++ = *B1++;
  198.     *pda = *pdb = *pde = NULL;
  199.  
  200.     return pde - E1;
  201. }
  202.  
  203.  
  204. /* rm2_contain -- perform containment between two arrays of set pointers */
  205. int rm2_contain(A1, B1)
  206. INOUT pset *A1;                 /* updated in place */
  207. IN pset *B1;                    /* unchanged */
  208. {
  209.     register pset *pa, *pb, a, b, *pdest = A1;
  210.  
  211.     /* for each set in the first array ... */
  212.     for(pa = A1; (a = *pa++) != NULL; ) {
  213.         /* for each set in the second array which is larger ... */
  214.         for(pb = B1; (b = *pb++) != NULL && SIZE(b) > SIZE(a); ) {
  215.             INLINEsetp_implies(a, b, /* when_false => */ continue);
  216.             /* set was contained in some set of B, so don't save pointer */
  217.             goto lnext1;
  218.         }
  219.         /* set wasn't contained in any set of B, so save the pointer */
  220.         *pdest++ = a;
  221.     lnext1: ;
  222.     }
  223.  
  224.     *pdest = NULL;                      /* sentinel */
  225.     return pdest - A1;                  /* # elements in A1 */
  226. }
  227.  
  228.  
  229.  
  230. /* sf_sort -- sort the sets of A */
  231. pset *sf_sort(A, compare)
  232. IN pset_family A;
  233. IN int (*compare)();
  234. {
  235.     register pset p, last, *pdest, *A1;
  236.  
  237.     /* Create a single array pointing to each cube of A */
  238.     pdest = A1 = (pset *) alloc((A->count+1)*sizeof(pset));
  239.     foreach_set(A, last, p) {
  240.         PUTSIZE(p, set_ord(p));         /* compute the set size */
  241.         *pdest++ = p;                   /* save the pointer */
  242.     }
  243.     *pdest = NULL;                      /* Sentinel -- never seen by sort */
  244.  
  245.     /* Sort cubes by size */
  246.     qsort((char *) A1, A->count, sizeof(pset), compare);
  247.     return A1;
  248. }
  249.  
  250.  
  251. /* sf_list -- make a list of pointers to the sets in a set family */
  252. pset *sf_list(A)
  253. IN register pset_family A;
  254. {
  255.     register pset p, last, *pdest, *A1;
  256.  
  257.     /* Create a single array pointing to each cube of A */
  258.     pdest = A1 = (pset *) alloc((A->count+1) * sizeof(pset));
  259.     foreach_set(A, last, p)
  260.         *pdest++ = p;                   /* save the pointer */
  261.     *pdest = NULL;                      /* Sentinel */
  262.     return A1;
  263. }
  264.  
  265.  
  266. /* sf_unlist -- make a set family out of a list of pointers to sets */
  267. pset_family sf_unlist(A1, totcnt, size)
  268. IN pset *A1;
  269. IN int totcnt, size;
  270. {
  271.     register pset pr, p, *pa;
  272.     pset_family R = sf_new(totcnt, size);
  273.  
  274.     R->count = totcnt;
  275.     for(pr = R->data, pa = A1; (p = *pa++) != NULL; pr += R->wsize)
  276.         INLINEset_copy(pr, p);
  277.     mem_free((char *) A1);
  278.     return R;
  279. }
  280.  
  281.  
  282. /* sf_merge -- merge three sorted lists of set pointers */
  283. pset_family sf_merge(A1, B1, E1, totcnt, size)
  284. INOUT pset *A1, *B1, *E1;               /* will be disposed of */
  285. IN int totcnt, size;
  286. {
  287.     register pset pr, pa, pb, pe;
  288.     register pset_family R = sf_new(totcnt, size);
  289.     pset *SA1 = A1, *SB1 = B1, *SE1 = E1;
  290.  
  291.     /* Merge the results of the three arrays */
  292.     R->count = totcnt;
  293.     pa = *A1++; pb = *B1++; pe = *E1++;
  294.  
  295.     for(pr = R->data; ; pr += R->wsize)
  296.         if (pa != NULL)
  297.             if (pb != NULL && desc1(pb, pa) < 0)
  298.                 if (pe != NULL && desc1(pe, pb) < 0)
  299.                     {INLINEset_copy(pr, pe); pe = *E1++;}
  300.                 else
  301.                     {INLINEset_copy(pr, pb); pb = *B1++;}
  302.             else
  303.                 if (pe != NULL && desc1(pe, pa) < 0)
  304.                     {INLINEset_copy(pr, pe); pe = *E1++;}
  305.                 else
  306.                     {INLINEset_copy(pr, pa); pa = *A1++;}
  307.         else
  308.             if (pb != NULL)
  309.                 if (pe != NULL && desc1(pe, pb) < 0)
  310.                     {INLINEset_copy(pr, pe); pe = *E1++;}
  311.                 else
  312.                     {INLINEset_copy(pr, pb); pb = *B1++;}
  313.             else
  314.                 if (pe != NULL)
  315.                     {INLINEset_copy(pr, pe); pe = *E1++;}
  316.                 else
  317.                    break;
  318.  
  319.     mem_free((char *) SA1);
  320.     mem_free((char *) SB1);
  321.     mem_free((char *) SE1);
  322.     return R;
  323. }
  324.